package main

import (
	"fmt"
	"sort"
)

func main() {
	candidates := []int{10, 1, 2, 7, 6, 1, 5}
	target := 8
	fmt.Print(combinationSum2(candidates, target))
}

func combinationSum2(candidates []int, target int) (ans [][]int) {
	size := len(candidates)
	sort.Ints(candidates)

	comb := []int{}
	var dfs func(residue int, begin int)
	dfs = func(residue int, begin int) {
		if residue == 0 {
			ans = append(ans, append([]int(nil), comb...))
		}

		for i := begin; i < size; i++ {
			if candidates[i] > residue {
				break
			}
			if i > begin && candidates[i-1] == candidates[i] {
				continue
			}
			comb = append(comb, candidates[i])
			dfs(residue-candidates[i], i+1)
			comb = comb[:len(comb)-1]
		}

	}

	dfs(target, 0)
	return

}
